Définition équivalente d'une congruence

Propriété  Définition équivalente à celle donnée précédemment

Soit \(a , b \in \mathbb{Z}\) et \(n \in \mathbb{N}^\ast\) . On a 
\(a \equiv b \ [n] \ \ \Longleftrightarrow \ \ a\)  et \(b\)  ont le même reste dans la division euclidienne par \(n\) .

 Exemples  Congruences modulo 7

• On a : \(30=4 \times 7+2\) et \(44=6 \times 7+2\) qui correspondent à des divisions euclidiennes par \(7\) avec le même reste \(2\) . Par conséquent : \(30 \equiv 44 \ [7]\) .
  
• Comme \(23=3 \times 7+2\) , on a aussi \(23 \equiv 30 \ [7]\) et \(23 \equiv 44 \ [7]\) .
  

Démonstration

On écrit les divisions euclidiennes de \(a\) et \(b\) par \(n\) :
\(a=nq+r\) avec \(0 \leqslant r 
et  \(b=nq'+r'\) avec  \(0 \leqslant r'.
En soustrayant les deux égalités, on obtient :
\(a-b=nq+r-nq'-r'=n(q-q')+(r-r')\)
De plus,  \(0 \leqslant r' < n \ \Longleftrightarrow \ -n<-r' \leqslant 0\) .
Comme  \(0 \leqslant r et  \(-n<-r' \leqslant 0\) , on obtient, en ajoutant ces inégalités,  \(-n.

Montrons l'équivalence souhaitée par double implication.

\([\Rightarrow]\) Supposons que \(a \equiv b \ [n]\) . Montrons que \(r=r'\) .
Alors \(a-b\) est un multiple de \(n\) , donc il existe \(k \in \mathbb{Z}\) tel que \(a-b=kn\) .
On a donc :
\(\begin{align*} a-b=n(q-q')+(r-r') & \ \ \Longleftrightarrow \ \ kn=n(q-q')+(r-r') \\ & \ \ \Longleftrightarrow \ \ r-r'=kn-n(q-q') \\ & \ \ \Longleftrightarrow \ \ r-r'=n(k-q+q') \end{align*}\)
donc \(r-r'\) est un multiple de \(n\) .
Comme  \(-n, on a nécessairement  \(r-r'=0\)  et donc  \(r=r'\) .

\([\Leftarrow]\) Supposons que \(r=r'\) .
On a alors \(a-b=n(q-q')\) , donc \(a-b\) est un multiple de \(n\) , donc \(a \equiv b \ [n]\) .